#pragma once
#include<iostream>
using namespace std;

enum Color
{
  RED,
  BLACK
};

template<class T>
struct RBTreeNode
{
    RBTreeNode<T>* _left;
    RBTreeNode<T>* _right;
    RBTreeNode<T>* _parent;
    
    //pair<K,V> _kv;
    T _data;
    Color _col;
    
    RBTreeNode(const T& data)
    :_left(nullptr)
    ,_right(nullptr)
    ,_parent(nullptr)
    ,_data(data)
    ,_col(RED)
    {}
};

//迭代器
template<class T>
struct __TreeIterator
{
    typedef RBTreeNode<T> Node;
    typedef __TreeIterator<T> self;
    Node* _node;
    
    __TreeIterator(Node* node):
    _node(node)
    {
        
    }

    
    T& operator *()
    {
        return _node->_data;
    }
    T& operator ->()
    {
        return _node->_data;
    }
    
    self& operator++()//++的核心，是找中序的下一个
    //1.it指向的节点，右子树不为空，下一个就是右子树的最左节点
    //2.it指向的节点，右子树为空，it中的节点所在的子树访问完了，往上找孩子是父亲左的那个祖先
    {
        if(_node->_right)//右子树不为空
        {
            //1.下一个就是右子树的最左节点
            Node* cur=_node->_right;
            while(cur->_left)
            {
                cur=cur->_left;
            }
            
            _node=cur;
        }
        else//右为空
        {
            //2.往上找孩子是父亲左的那个祖先
            Node* cur=_node;
            Node* parent=cur->_parent;
            while(parent&&cur!=parent->_left)
            {
                cur=parent;
                parent=cur->_parent;
            }
            _node=parent;
        }
        return *this;
    }
    
    bool operator!=(const self& s)
    {
        return _node!=s._node;
    }
};


//RBTree<K,K,SetKeyOfT> _t;
// RBTree<K,pair<K,T>,MapKeyOfT> _t;
template<class K,class T,class KeyOfT>
class RBTree
{
    typedef RBTreeNode<T> Node;
public:
    typedef __TreeIterator<T> iterator;
public:
    
    iterator begin()
    {
        Node* cur=_root;
        while(cur&&cur->_left)//去找树的最左节点
        {
            cur=cur->_left;
        }
        return iterator(cur);
    }
    
    iterator end()
    {
        return iterator(nullptr);
    }
    
    bool Insert(const T& data)
    {
        if(_root==nullptr)
        {
            _root=new Node(data);
            _root->_col = BLACK;
            return true;
        }
        
        Node* parent=nullptr;
        Node* cur=_root;
        KeyOfT kot;//仿函数对象
        
        while(cur)
        {
            if(kot(cur->_data)<kot(data))
            {
                parent=cur;
                cur=cur->_right;
            }
            else if(kot(cur->_data)>kot(data))
            {
                parent=cur;
                cur=cur->_left;
            }
            else
            {
                return false;
            }
        }
        cur=new Node(data);
        cur->_col=RED;//新增节点为红色
        
        
        if(kot(parent->_data)<kot(data))
        {
            parent->_right=cur;
            cur->_parent=parent;//将节点的父指针指向父亲
        }
        else
        {
            parent->_left=cur;
            cur->_parent=parent;//将节点的父指针指向父亲
        }
            
        while(parent && parent->_col==RED)
        {
            //      g
            //  p       u
            //c
            Node* grandfather=parent->_parent;

            if(parent==grandfather->_left)//如果p是g左节点，则u是g的右节点
            {
                Node* uncle=grandfather->_right;
                if(uncle&& uncle->_col==RED)
                {
                    //变色
                    parent->_col=uncle->_col=BLACK;
                    grandfather->_col=RED;
                    
                    cur=grandfather;//继续往上更新处理
                    parent=cur->_parent;
                }
                else//情况2
                {
                    if(cur==parent->_left)
                    {
                        //单旋
                        //      g
                        //  p
                        //c
                        RotateR(grandfather);
                        
                        parent->_col=BLACK;
                        grandfather->_col=RED;
                    }
                    else
                    {
                        //双旋
                        //      g
                        //  p
                        //      c
                        RotateL(parent);
                        RotateR(grandfather);
                        
                        //为什么cur->_col=BLACK呢？情况二的处理方法不是p为黑、g为红吗？这是由于这里要经过两次旋转，第一次旋转的时候，p和c交换了位置，但是我们这里并没有p和c的指向，按理来说更改p、c指向，再按照情况二处理方法是没错的。
                        cur->_col=BLACK;
                       // parent->_col=BLACK;
                        grandfather->_col=RED;
                    }
                    break;
                }
            }
            else
            {
                Node* uncle=grandfather->_left;
                if(uncle&&uncle->_col==RED)
                {
                    parent->_col=uncle->_col=BLACK;
                    grandfather->_col=RED;
                    
                    cur=grandfather;//继续往上进行处理
                    parent=cur->_parent;
                }
                else
                {
                    if(cur==parent->_right)
                    {
                        //单旋
                        RotateL(grandfather);
                        
                        parent->_col=BLACK;
                        grandfather->_col=RED;
                    }
                    else
                    {
                        RotateR(parent);
                        RotateL(grandfather);
                        
                        cur->_col=BLACK;
                        //parent->_col=BLACK;
                        grandfather->_col=RED;
                    }
                    break;
                }
            }
        }
        //如果向上更新的时候，grandfather不是根，就继续向上进行更新，如果grandfather是根怎么办呢？因为我们需满足RB树的根节点必须是黑色的，其实很简单，跳出更新循环（通过在while条件里判断parent为空实现的），然后直接让根节点为黑色_root->_col=BLACK
        _root->_col=BLACK;
        
        return true;
    }
    
    void RotateL(Node* parent)//左单旋
    {
        Node* subR=parent->_right;
        Node* subRL=subR->_left;
        //用于记录parent的parent，因为左旋转的时候，不一定parent是根
        Node* parentParent=parent->_parent;
        
        parent->_right=subRL;
        subR->_left=parent;
        
        parent->_parent=subR;
        if(subRL)
            subRL->_parent=parent;
        
        //如果parent是整个树的根
        if(_root==parent)
        {
            _root=subR;
            subR->_parent=nullptr;
        }
        //如果parent不是是整个树的根
        else
        {
            //将parentParent的左指向subR
            if(parentParent->_left==parent)
                parentParent->_left=subR;
            //将parentParent的右指向subR
            else
                parentParent->_right=subR;
            //subR的parent指向parentParent
            subR->_parent=parentParent;
        }
    }
    
    void RotateR(Node* parent)//右单旋
    {
        Node* subL=parent->_left;
        Node* subLR=subL->_right;
        Node* parentParent=parent->_parent;
        
        parent->_left=subLR;
        subL->_right=parent;
        
        parent->_parent=subL;
        if(subLR)
            subLR->_parent=parent;
        
        if(_root==parent)
        {
            _root=subL;
            subL->_parent=nullptr;
        }
        else
        {
            if(parentParent->_left==parent)
                parentParent->_left=subL;
            else
                parentParent->_right=subL;
            subL->_parent=parentParent;
        }
    
    }
    
    void _InOder(Node* root)
    {
        if(root==nullptr)
            return;
        _InOder(root->_left);
        cout<<root->_kv.first<<" ";
        _InOder(root->_right);
    }
    void InOrder()
    {
        _InOder(_root);
        cout<<endl;
    }
    
    // 根节点->当前节点这条路径的黑色节点的数量
        bool Check(Node* root, int blacknum, const int refVal)
        {
            if (root == nullptr)
            {
                //cout << blacknum << endl;
                if (blacknum != refVal)
                {
                    cout << "存在黑色节点数量不相等的路径" << endl;
                    return false;
                }

                return true;
            }

            if (root->_col == RED && root->_parent->_col == RED)
            {
                cout << "有连续的红色节点" << endl;

                return false;
            }

            if (root->_col == BLACK)
            {
                ++blacknum;
            }

            return Check(root->_left, blacknum, refVal)
                && Check(root->_right, blacknum, refVal);
        }

        bool IsBalance()
        {
            if (_root == nullptr)
                return true;

            if (_root->_col == RED)
                return false;

            //参考值
            int refVal = 0;
            Node* cur = _root;
            while (cur)
            {
                if (cur->_col == BLACK)
                {
                    ++refVal;
                }

                cur = cur->_left;
            }

            int blacknum = 0;
            return Check(_root, blacknum, refVal);
        }
    
private:
    Node* _root=nullptr;
};

